//https://leetcode.cn/problems/implement-queue-using-stacks/submissions/530510887/
//用两个栈实现队列
//请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

//实现 MyQueue 类：

//void push(int x) 将元素 x 推到队列的末尾
//int pop() 从队列的开头移除并返回元素
//int peek() 返回队列开头的元素
//boolean empty() 如果队列为空，返回 true ；否则，返回 false

typedef int STDataType;

typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}Stack;

//初始化
void STInit(Stack* pst);
//销毁
void STDestroy(Stack* pst);
//插入
void STPush(Stack* pst, STDataType x);
//删除
void STPop(Stack* pst);
//获取栈顶数据
STDataType STTop(Stack* pst);
//判断是否为空
bool STEmpty(Stack* pst);
//剩余数据个数
int STSize(Stack* pst);

void CheckCapacity(Stack* pst)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = (pst->capacity == 0) ? 4 : (pst->capacity * 2);
		STDataType* tmp = (STDataType*)realloc(pst->data, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		pst->data = tmp;
		pst->capacity = newcapacity;
	}
}

//初始化
void STInit(Stack* pst)
{
	assert(pst);
	pst->data = NULL;
	//top指向栈顶数据的下一个位置
	pst->top = 0;
	pst->capacity = 0;
}

//销毁
void STDestroy(Stack* pst)
{
	assert(pst);
	free(pst->data);
	pst->capacity = 0;
	pst->top = 0;
}

//插入
void STPush(Stack* pst, STDataType x)
{
	assert(pst);
	CheckCapacity(pst);
	pst->data[pst->top++] = x;
}

//删除
void STPop(Stack* pst)
{
	assert(pst);
	if(pst->top > 0)
	pst->top--;
}

//获取栈顶数据
STDataType STTop(Stack* pst)
{
	assert(pst);
	assert(!STEmpty(pst));

	return pst->data[pst->top - 1];
}

//判断是否为空
bool STEmpty(Stack* pst)
{
	assert(pst);
	return pst->top == 0;
}

//剩余数据个数
int STSize(Stack* pst)
{
	assert(pst);
	return pst->top;
}

enum States
{
    PUSH,
    POP
};

typedef struct {
    enum States state;
    Stack sti;//入
    Stack sto;//出
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    obj->state = PUSH;
    STInit(&obj->sti);
    STInit(&obj->sto);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    if(obj->state != PUSH)
    {
        while(!STEmpty(&obj->sto))
        {
            STPush(&obj->sti, STTop(&obj->sto));
            STPop(&obj->sto);
        }
        obj->state = PUSH;
    }

    STPush(&obj->sti, x);
}

int myQueuePop(MyQueue* obj) {
    if(obj->state != POP)
    {
        while(!STEmpty(&obj->sti))
        {
            STPush(&obj->sto, STTop(&obj->sti));
            STPop(&obj->sti);
        }
        obj->state = POP;
    }

    int ret = STTop(&obj->sto);
    STPop(&obj->sto);
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    if(obj->state != POP)
    {
        while(!STEmpty(&obj->sti))
        {
            STPush(&obj->sto, STTop(&obj->sti));
            STPop(&obj->sti);
        }
        obj->state = POP;
    }

    int ret = STTop(&obj->sto);
    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    return (STEmpty(&obj->sti) && STEmpty(&obj->sto));
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->sti);
    STDestroy(&obj->sto);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/